package com.ryujung.array.leetCode_1299;

/**
 * @author RyuJung
 * @date 2020-2-9 23:09
 */
public class Solution {
    public int[] replaceElements(int[] arr) { //暴力解法 ,时间复杂度n^2
        for (int i = 0; i < arr.length - 1; i++) {
            arr[i] = arr[i + 1];
            for (int j = i; j < arr.length; j++) {
                if (arr[i] < arr[j]) {
                    arr[i] = arr[j];
                }
            }
        }
        arr[arr.length - 1] = -1;
        return arr;
    }

    public int[] replaceElements2(int[] arr) { //倒序遍历,递推方式取最大值
        int n = arr.length;
        int[] ans = new int[n];
        for (int i = n - 1; i > 0; i--) {
            ans[i - 1] = Math.max(ans[i], arr[i]);
        }
        ans[n - 1] = -1;
        return ans;
    }

    public int[] replaceElements3(int[] arr) { //倒序遍历,记录最大值
        int n = arr.length;
        int[] ans = new int[n];
        int t = 0;  //记录最大值
        for (int i = n - 2; i >= 0; i--) {
            if (t < arr[i + 1]) t = arr[i + 1]; //如果逆向遍历遇到更大的值,就将t替换
            ans[i] = t;
        }
        ans[n - 1] = -1;  //将最后一位赋值-1
        return ans;
    }

    public void test() {
        int[] ints = replaceElements3(new int[]{17, 18, 5, 4, 6, 1});
    }
}
